// #include<bits/stdc++.h>
// #define sd(n) scanf("%d",&n) 
// #define sld(n) scanf("%lld",&n)
// #define pd(n) printf("%d", (n))
// #define pld(n) printf("%lld", n)
// #define all(x) (x).begin(),(x).end()
// #define rall(x) (x).rbegin(),(x).rend()
// #define fi first
// #define se second
// const int N=2e5;
// const int maxn=1e6;
// typedef long long int ll;
// using namespace std;
// //----------------------------------------------------------------------------//

// void solve()
// {
// 	int n,k;
// 	sd(n);sd(k);
// 	string s;
// 	cin>>s;
// 	int st[40];//存字母个数
// 	memset(st,0,sizeof(st));
// 	int cnt=0;

// 	for(int i=0;i<s.size();i++)
// 	{
// 		st[s[i]-'a']++;
// 	}

// 	int ans=0;
// 	int t=0;

// 	for(int i=0;i<=25;i++)
// 	{
// 		if(st[i]%2!=0)
// 			t++;
// 		ans+=st[i]/2;
// 	}

// 	t+=2*(ans%k);
// 	ans/=k;
// 	if(t>=k) ans=ans*2+1;
// 	else ans*=2;
// 	pd(ans);
// 	puts("");

// }

// int main()
// {
// 	int T;
// 	sd(T);
// 	while (T--)
// 	{
// 		solve();
// 	}
// 	return 0;
// }



#include<bits/stdc++.h>
#define sd(n) scanf("%d",&n) 
#define sld(n) scanf("%lld",&n)
#define pd(n) printf("%d", (n))
#define pld(n) printf("%lld", n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
const int N=2e5;
const int maxn=1e6;
typedef long long int ll;
using namespace std;
//----------------------------------------------------------------------------//
int a[26];
void solve()
{
	int n,k;cin>>n>>k;
	string s;cin>>s;
	memset(a,0,sizeof a);
	int cnt=0;//cnt表示偶数的对数
	for(int i=0;i<=n-1;i++) a[s[i]-'a']++;
	for(int i=0;i<=25;i++) cnt+=a[i]/2;
	cout<<cnt/k*2+((n-cnt/k*k*2)/k>0)<<endl;//n-cnt/k*k*2即没有用到的字符数量


}

int main()
{
	int T;
	sd(T);
	while (T--)
	{
		solve();
	}
	return 0;
}